#include<bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head)return head;
        ListNode* fast = head, *slow = head;
        do{
            if(fast && fast->next){
                fast = fast->next->next;
            }else{
                return nullptr;
            }
            slow = slow->next;
        }while(fast != slow);

        //到这说明有环
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

/**
 * @brief 2022.4.27
 * 快慢指针确定是否有环
 * 再遍历一遍确定环的入口
 */